package graph.algorithm;

import graph.Edge;
import graph.Graph;
import graph.Node;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RegionFinder {
	private Graph<?, ?> graph;

	public RegionFinder(Graph<?, ?> graph) {
		this.graph = graph;
	}
    public Set<List<Node<?>>> findRegions() {
        HashSet<Edge<?, ?>> forwardSet = new HashSet<Edge<?,?>>();
        HashSet<Edge<?, ?>> backwardSet = new HashSet<Edge<?,?>>();
        Set<List<Node<?>>> result = new HashSet<List<Node<?>>>();
        for (Edge<?, ?> edge : graph.getEdges()) {
            process(edge, forwardSet, backwardSet, result);
        }
        return result;
    }

    private void process(Edge<?, ?> edge, HashSet<Edge<?, ?>> forwardSet,
            HashSet<Edge<?, ?>> backwardSet, Set<List<Node<?>>> result) {
        if (!forwardSet.contains(edge)) {
            forwardSet.add(edge);
            List<Node<?>> loop = getRegion(edge.a, edge.b, forwardSet, backwardSet);
            result.add(loop);
        }
        if (!backwardSet.contains(edge)) {
            backwardSet.add(edge);
            List<Node<?>> loop = getRegion(edge.b, edge.a, forwardSet, backwardSet);
            result.add(loop);
        }
    }

    private List<Node<?>> getRegion(Node<?> a, Node<?> b,
            HashSet<Edge<?, ?>> forwardSet, HashSet<Edge<?, ?>> backwardSet) {
    	ArrayList<Node<?>> result = new ArrayList<Node<?>>();
    	double minAngle = 2*Math.PI;
    	for (Node<?> n : graph.getNeighbours(a)) {
    		if (n == a) continue;
    		double angle = angle(a, b, n);
    		
    		
    	}
    	return result;
    }
	private double angle(Node<?> a, Node<?> b, Node<?> c) {
		double dx1 = a.pos.x-b.pos.x;
		double dy1 = a.pos.y-b.pos.y;
		double dx2 = c.pos.x-b.pos.x;
		double dy2 = c.pos.y-b.pos.y;
		double a1 = Math.atan2(dy1, dx1);
		double a2 = Math.atan2(dy2, dx2);
		double angle = a2-a1;
		if (angle < 0) angle += 2*Math.PI;
		return angle;
	}

}